﻿#include <stdio.h>
#include <stdbool.h>

// show debug log
static bool isDebug = true;

// 打印数组
void printArray(int* ary, int len) {
	if (len == 0) {
		printf("[]");
		return;
	}
	// 字符串
	for (int i = 0; i < len; i++)
	{
		// 用数组‘,’形式分隔元素
		printf(i == 0 ? "[" : ",");
		printf("%d", ary[i]);
	}
	printf("]\n");
}

void insertionSort(int arr[], int len)
{
	if (len <= 1 || !arr) return;
	if (isDebug) {
		printf("数组长度%d，排序前数组：\n", len);
		printArray(arr, len);
	}
	for (int i = 1; i < len; i++)
	{
		int tarPos = i - 1;		// 目标位置(从当前位置前一个开始，向前查找)
		const int val = arr[i]; // 当前数值(做替换准备)
		while (tarPos >= 0 && arr[tarPos] > val) {
			arr[tarPos + 1] = arr[tarPos];
			tarPos--;
		}
		// 指针停止，指针的下一个位置就是正确的序列位置
		arr[tarPos + 1] = val;
		if (isDebug) {
			printf("从数组位置%d开始搜索，目标元素位置为%d，排序后数组：\n", i, tarPos + 1);
			printArray(arr, len);
		}
	}
}

int main() {
	int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
	const int len = (int)sizeof(arr) / sizeof(*arr);
	insertionSort(arr, len);
	return 0;
}
